﻿#include <iostream>     // std::cout
#include <algorithm>    // std::reverse
#include <list>﻿
#include <string>
#include <queue>

//https://leetcode.cn/problems/min-stack/description/
//设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
//
//实现 MinStack 类 :
//
//MinStack() 初始化堆栈对象。
//void push(int val) 将元素val推入堆栈。
//void pop() 删除堆栈顶部的元素。
//int top() 获取堆栈顶部的元素。
//int getMin() 获取堆栈中的最小元素。

#include <stack>

class MinStack {
public:
    MinStack()
    {
        //会自动调用构造函数
        min_st.push(INT_MAX);
    }

    void push(int val)
    {
        st.push(val);
        min_st.push(min(val, min_st.top()));

    }

    void pop()
    {
        st.pop();
        min_st.pop();
    }

    int top()
    {
        return st.top();
    }

    int getMin()
    {
        return min_st.top();
    }

    stack<int> st;
    stack<int> min_st;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */


//https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
//输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1, 2, 3, 4, 5是某栈的压入顺序，序列4, 5, 3, 2, 1是该压栈序列对应的一个弹出序列，但4, 3, 5, 1, 2就不可能是该压栈序列的弹出序列。
//1. 0 <= pushV.length == popV.length <= 1000
//2. - 1000 <= pushV[i] <= 1000
//3. pushV 的所有数字均不相同


class Solution {
public:

    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        stack<int> st;
        int pushi = 0, popi = 0;
        int size = pushV.size();
        while (pushi < size)
        {
            while (pushi < size && pushV[pushi] != popV[popi])
            {
                st.push(pushV[pushi]);
                ++pushi;
            }
            while (pushi < size && pushV[pushi] == popV[popi])
            {
                ++pushi;
                ++popi;
            }
            while (pushi < size && !st.empty() && st.top() == popV[popi])
            {
                st.pop();
                ++popi;
            }
        }
        while (pushi == size)
        {
            if (!st.empty() && st.top() == popV[popi])
            {
                st.pop();
                ++popi;
            }
            else if (st.empty() && popi == size)
            {
                return true;
            }
            else
            {
                return false;
            }

        }

        return false;
    }
};



//https://leetcode.cn/problems/kth-largest-element-in-an-array/description///215. 
// 数组中的第K个最大元素
//已解答
//中等
//相关标签
//相关企业
//给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
//
//请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
//
//你必须设计并实现时间复杂度为 O(n) 的算法解决此问题


#include <queue>

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        priority_queue<int, vector<int>, greater<int >>  q;
        for (auto e : nums)
        {
            if (q.size() < k)
                q.push(e);
            else if (e > q.top())
            {
                q.pop();
                q.push(e);
            }
        }

        return q.top();
    }
};

using namespace std;



void func1()
{


        priority_queue<int> a;

        priority_queue<int, vector<int>, greater<int> > c;

        priority_queue<string> b;

        for (int i = 0; i < 5; i++)

        {

            a.push(i);

            c.push(i);

        }

        while (!a.empty())

        {

            cout << a.top() << ' ';

            a.pop();

        }

        cout << endl;

        while (!c.empty())

        {

            cout << c.top() << ' ';

            c.pop();

        }

        cout << endl;

        b.push("abc");

        b.push("abcd");

        b.push("cbd");

        while (!b.empty())

        {

            cout << b.top() << ' ';

            b.pop();

        }
        cout << endl;

}


void func2()
{

    int ar[] = { 0,1, 2, 3, 4,  5, 6, 7, 8, 9 };

    int n = sizeof(ar) / sizeof(int);

    list<int> mylist(ar, ar + n);

    list<int>::iterator pos = find(mylist.begin(), mylist.end(), 5);

    reverse(mylist.begin(), pos);
    //左闭右开

    reverse(pos, mylist.end());
    list<int>::const_reverse_iterator crit = mylist.crbegin();

    while (crit != mylist.crend())

    {

        cout << *crit << " ";

        ++crit;

    }

    cout << endl;


}

int main()

{
    func1();
	return 0;
}
